1. Field of the Invention
The present invention relates generally to algorithms for mapping elements between two sets and, more particularly, to algorithms for repeatedly mapping elements between two sets based on random keys so as to dynamically provide random mappings. Such dynamic mapping algorithms can be applied to memory address spaces to effect wear leveling techniques; and more particularly, wear leveling techniques for mitigating worst-case wear scenarios including malicious attacks and/or compromised operating systems.
2. Description of the Related Art
Phase change memory (PCM) has emerged as a potential memory technology for improving the performance of the overall system memory hierarchy. A PCM cell can be made of phase-change material based on chalcogenide alloys commonly composed of the elements Germanium (Ge), Antimony (Sb), and Tellurium (Te). Such materials have at least two distinct phases—a high electrical resistive amorphous phase and a low resistive crystalline phase. The crystalline phase can be reached by heating the material above the crystallization temperature while the material can be switched into the amorphous phase by melting and quickly quenching. A data bit can be stored in either state, both of which are non-volatile.
Recently, researchers have studied the trade-off of using PCM as the main memory, or even as the last level cache. The density of PCM is currently higher than that of dynamic random-access memory (DRAM) and expected to increase. Moreover, PCM promises better scalability with process technology scaling. And although the latency of PCM is currently several times higher than DRAM, several studies showed that the benefits gained from its high density can outweigh the degradation of access time by employing a deeper memory hierarchy or employing a hybrid-memory architecture with mixed usage of other memory technologies.
The primary roadblock for using PCM as part of the main memory is its much lower write endurance compared to DRAM. The current write endurance of a PCM cell is around 10^8. Several recent studies have attempted to address this issue by either reducing PCM's write frequency or using wear-leveling techniques to evenly distribute PCM writes. Although these techniques can extend the lifetime of PCM under normal operations of typical applications, most of them fail to prevent an adversary from writing malicious code deliberately designed to wear out and fail PCM. For instance, schemes to reduce write frequency, such as data comparison write (B.-D. Yang, J.-E. Lee, J.-S. Kim, J. Cho, S.-Y. Lee, and B.-G. Yu, “A Low Power Phase-Change Random Access Memory using a Data-Comparison Write Scheme,” in Proc. IEEE International Symposium on Circuit and Systems, 2007) and Flip-N Write (S. Cho and H. Lee, “Flip-N-Write: A Simple Deterministic Technique to Improve PRAM Write Performance, Energy and Endurance,” in Proc. of the International Symposium on Microarchitecture, 2009) do not prevent an adversary from wiggling the memory bits of the same PCM location and wearing them out. Previous wear-leveling schemes are also vulnerable due to the inherent weaknesses caused by static randomization, coarse-grained shuffling, and regular pattern shuffling.
Furthermore, prior attempts do not consider circumstances when the underlying operating system (OS) is compromised and the resulting security implications to PCM design. A compromised OS, (e.g., via buffer overflow) can allow adversaries to manipulate all processes and easily exploit side channels, accelerating the wear-out of targeted PCM blocks and rendering a dysfunctional system. For example, a compromised OS can thrash or turn off all caches, disabling a shield that protects the PCM. Moreover, if the compromised OS allows a malicious process to obtain and assemble useful information leaked from side channels (e.g., timing attacks to deduce the shuffling pattern in a wear-leveling scheme), the wear-leveling scheme will not stop adversaries from tracking, pinpointing, and wearing out target PCM blocks. Attacking a system with side channels using time, power, electromagnetic emission, architectural vulnerability, etc., have all been successfully demonstrated in many systems including the Microsoft© Xbox©. Designing PCM without careful consideration for these security implications risks computationally inaccurate results and critical data loss, potentially leading to dire financial consequences.